//
// Description: 931. 下降路径最小和
// Created by Loading on 2022/7/3.
//

#include <bits/stdc++.h>

using namespace std;

int minFallingPathSum(vector<vector<int>> &matrix) {
    int n = matrix.size();

    int dp[n][n + 2];
    memset(dp, 0x3f, sizeof dp);

    for (int i = 0; i < n; ++i) {
        dp[0][i + 1] = matrix[0][i];
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i][j - 1];
        }
    }

    return *min_element(dp[n - 1] + 1, dp[n - 1] + 1 + n);
}

int main() {
    vector<vector<int>> matrix{{2, 1, 3},
                               {6, 5, 4},
                               {7, 8, 9}};

    int res = minFallingPathSum(matrix);

    cout << res << endl;

    return 0;
}
